COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "book.pub[let,jmc]" source_file
C00009 ENDMK
C⊗;
.require "book.pub[let,jmc]" source_file;
.font B "ms25";
.font C "grfx25"
.font D "grfx35"
.TURN OFF "{}∂[]"
.cb	CS206	Computing with Symbolic Expressions	Spring 1977
.cb	Problem Set 2
.cb	Due May 12
.skip 2
Write and debug the following LISP functions. Submit printed output containing
a prettyprint of each function and examples showing the results of the functions.

1. Unification:

Let %2vars%1 be a list of atoms to be called variables, all others being
considered to be constants. In our examples we will take %2vars%1 = (U V W X Y
Z). An %2association list%1 or %2a-list%1 for short, is a list of pairs such that
the first element of each pair is associated with a second element which
can be any s-expression. An example of an a-list showing a possible set of
assignments for our variables could be %2w1%1 = ((X.A)(Y.(B.C))(X A B
C)(W.(X.A)).  Note that the same first element can appear in more than one
pair; the function %2assoc%1 only sees the first occurrence.
.skip 1
.nofill
The function 

%2sublis[w,x] ← %3if at %2x %3then %1{%2assoc%1[%2x,w%1]}[%2λz.%3if n %2z %3then %2x %3else d %2z%1] 
		%3else %2sublis%1[%2w,%3a %2x%1].%2sublis%1[%2w,%3d %2x%1] 
.fill
gives the result of simultaneously
substituting for the variables of %2w%1 the s-expressions that are paired with
them. Thus 

%2sublis%1[%2w1%1,(X X A W Y)] = (A A A (X.A)(B.C))

and

%2sublis%1[((X TIMES A B)(Y.C)),(PLUS X Y)] = (PLUS (TIMES A B) C).

Sublis has an inverse of sorts called inst defined as follows;

.nofill

%2inst[pat,exp,w] ←
  %3if %2w = %1NO %3then %1NO
  %3elseif at %2pat %3then 
	%2[%3if %2pat %3ε %2vars %3then %2{assoc [pat,w]}[λz.%3if n %2z %3then %2[pat.exp].w
						%3elseif d %2z %3equal %2exp %3then%2 w
						%3else %1NO]
	%3elseif %2pat %3eq %2exp %3then %2w
	%3else %1NO]
  %3elseif at %2exp %3then %1NO
  %3else %2inst[%3d %2pat, %3d %2exp, inst[%3a %2pat,%3a %2exp,w]]%1

.fill

inst is an inverse of sublis in the sense that 
%2inst[pat,exp,w] %1≠ NO implies %2sublis[inst[pat,exp,w],pat]=exp%1.

%2inst%1 and %2sublis%1 are used in programs that symbolically transform expressions
according to rules like the following:

(TIMES (PLUS X Y)(DIFFERENCE X Y)) → (DIFFERENCE (POWER X 2)(POWER Y 2)).

A related concept is called unification. We say that %2x1%1 and %2x2%1 unify to %1x%2
if there exist %2w1%1 and %2w2%1 such that:

%2x=sublis[w1,x1]=sublis[w2,x2]%1

Assuming our conventions on variables and constants, (A X) and (X B)
unify to (A B), and (A X) and (B X) don't unify. If %2x1%1 and %2x2%1 have no
variables in common, a single a-list %2w%1 can be used. We say that %2w%1 unifies
%2x1%1 and %2x2%1 to %2x%1 if and only if

%2x=sublis[w,x1]=sublis[w,x2].%1

Thus the a-list ((X.A)(Y.A)) unifies (A X) and (A Y) to (A A) and ((X.Y))
unifies them to (A Y). The latter is more general in the sense that (A A)
is an instance of (A Y) and the converse statement is not true. If %2x1%1 and
%2x2%1 unify at all, there are %2most general unifiers%1 which differ from one
another only by a renaming of the variables.

Write a LISP function for %2unify[x1,x2]%1 whose value is NO if %2x1%1 and %2x2%1 can't be
unified and a most general unifier otherwise. Examples of the function follow:

%2unify%1[(A X),(A Y)] = ((X.Y))

%2unify%1[(A (B X) Y), (A U (C V))] = ((U B X)(YC V)).

To simplify matters, you may assume that %2x1%1 and %2x2%1 have no variables in common.


2. Write a LISP function to convert a recursive function definition to a PROG
using SETQ's and GO's instead of the function calls. Design your function so
that it only makes the change when it is correct to do so.

3. The compilers described in the class notes convert a LISP program to an
assembly language form called LAP code. The conversion from this code to actual
machine code is of less theoretical interest than the compilation process, but
it is necessary to do it at some point. Write a function %2slowlap[x]%1 which takes
the LAP code produced by a compiler and returns a list of the actual code. You
can put the machine code values for the nmemonics on their property lists. This
assembler need only cover the codes necessary for the example compilation of %2alt%1
in the class notes.